1. Technical Field
The invention relates generally to computer graphics systems, and, more particularly, to computer graphics systems that provide real-time interactive visualization of complex geometric models.
2. Description of the Related Art
Traditional computer graphics systems are used to model a scene of three-dimensional objects and render the scene for display on a two-dimensional display device such as a cathode ray tube or liquid crystal display. Typically, the three-dimensional objects of the scene are each represented by a multitude of polygons (or primitives) that approximate the shape of the object. The primitives that define an object are typically defined by coordinates in a local coordinate system. For example, one of the primitives that may be used to define an object is a triangle, which is defined by the coordinates of three vertices in the local coordinate system.
The rendering of a scene conventionally is divided into two stages: geometry processing and rasterization. Geometry processing typically includes a modeling transformation, lighting calculations, a viewing transformation, a clipping function, and viewport mapping. The modeling transformation transforms the primitives from the local coordinate system to a world coordinate system. The lighting calculations evaluate an illumination model at various locations: once per primitive for constant shading, once per vertex for Gouraud shading, or once per pixel for Phong shading. The viewing transformation transforms the primitives in world coordinates to a 3D screen coordinate system (sometimes referred to as the normalized projection coordinate system). The clipping function determines the primitives (or portions of the primitives) that are within the viewing frustrum. And viewport mapping maps the coordinates of the clipped primitives to the normalized device coordinate system (sometimes referred to as the 2D device coordinate system).
Rasterization is the process which converts the description of the clipped primitives generated during geometry processing into pixels for display. A typical primitive, as shown in FIG. 1A, is a triangle T.sub.1. Other area or surface primitives conventionally are converted into one or more triangles prior to rasterization. Consequently, the conventional rasterization process need only to handle triangles. The triangle T.sub.1 is represented by the (x,y,z) coordinates at each of its vertices. The (x,y) coordinates of a vertex tell its location in the plane of the display. The z coordinate tells how far the vertex is from the selected view point of the three-dimensional scene. Rasterization is typically divided into three tasks: scan conversion, shading, and visibility determination.
Scan conversion utilizes the (x,y) coordinates of the vertices of each triangle to compute a set of pixels S which is covered by the triangle.
Shading computes the colors of the set of pixels S covered by each triangle. There are numerous schemes for computing colors, some of which involve computationally intensive techniques such as texture mapping. Shading typically utilizes the lighting calculations described above with respect to geometric processing.
Visibility determination utilizes the z coordinate of each triangle to compute the set of pixels S.sub.v (a subset of S) which are "visible" for the triangle. The set S.sub.v will differ from the set S if any of the pixels in set S are covered by previously rasterized triangles whose z values are closer to the selected view point. Thus, for each triangle in the scene as described by all previously processed triangles, a pixel is "visible" if it is in the set S.sub.v or "hidden" if it is the set S but not in the set S.sub.v. Moreover, a triangle is "all visible" if the set S.sub.v is identical to set S, "partially hidden" if the set S.sub.v is not identical to set S and set S.sub.v is not empty, or "all hidden" if set S.sub.v is empty. For example, FIG. 1B shows two triangles, triangle T1 and T2, wherein triangle T1 is partially hidden by triangle T2. Visibility determination is traditionally accomplished using a z-buffer technique. The Z-buffer stores an entry for each pixel that represents the z-value of the visible primitive at the given pixel. The z-value (Znew) of a set of pixels covered by a given triangle is determined through interpolation. For each pixel within the set, Znew at the given pixel is compared to the z-value (Zold) stored as an entry in the Z-buffer corresponding to the given pixel, and the entry Zold is updated with Znew according to results of the compare operation.
Rasterization is completed by writing the colors of the set of visible pixels S.sub.v to an image buffer for display.
As scenes become more and more complex, traditional rendering techniques are too computationally intensive for many graphics systems and result in degraded performance. Alternate rendering techniques suitable for complex scenes have been proposed. For example, U.S. Pat. No. 5,086,496, to Mulmuley, entitled "Method for Hidden Line and Surface Removal in a Three Dimensional Display" utilizes stripped partitions of the viewing window (which are defined by boundaries that intersect at least one image vertex) and visibility pointers to faces that are visible within a given partition to perform the visibility determination of the faces.
In another example, Green et al., "Hierarchical Z-Buffer Visibility", Proc. ACM SIGGRAPH 93, pp. 231-238, 1993, describe a combination of two hierarchical data structures, an object-space octree and an image-space Z-pyramid, to accelerate scan conversion.
In addition, Teller et al., "Visibility Preprocessing for Interactive Graphics", Proc. ACM SIGGRAPH 91, pp. 61-69, 1991, describes an algorithm utilized during a visibility preprocessing phase that subdivides a model into a plurality of cells and generates cell-to-cell visibility information (which represents, for a given cell, the set of cells that are partially or completely visible from at least one point within the given cell). During an interactive walkthrough phase, an observer with a known position and view frustrum moves through the model. At each frame, the cell containing the observer is identified, and the contents of potentially visible cells (which is derived from the cell-to-cell visibility information generated during the preprocessing phase) are retrieved from storage. The set of potentially visible cells is further reduced by culling it against the observer's view frustrum to produce eye-to-cell information (which represents the set of cells that are partially or completely visible to an observer within the specified view frustrum). The contents of the remaining visible cells, as identified by the eye-to-cell information, are then sent to a graphics pipeline for hidden-surface removal and rendering. Teller et al., "Global Visibility Algorithms for Illumination Computations", Proc. ACM SIGGRAPH 93, pp. 239-246, 1993, applies these visibility pre-processing algorithms to radiosity computations.
Although such alternate techniques are designed to accelerate visibility determination during rasterization, these techniques are inflexible and in most instances add computationally intensive tasks to the rendering process that outweigh their benefits. Thus, there is a need in the art to provide for flexible rendering techniques that can be tailored to meet the requirements dictated by the varying complexity and characteristics found in today's three-dimensional models and scenes.